package com.cet.test.mt04.qz4;

/**
 * @program: cet-practice
 * @description:
 * @author: 陈恩涛
 * @create: 2023-05-06 21:42
 **/
public class Client {

    public static void main(String[] args) {
        Node l1 = Node.init(9, 0, 0, 1);
        Node l2 = Node.init(1, 3);
        System.out.println(sub(l1, l2));
    }

    /**
     * 链表减法
     * @param n1 被减数链表头结点
     * @param n2 减数链表头结点
     * @return 差链表
     */
    static Node sub(Node n1, Node n2) {

        // 运算数倒序，方便单链表低位向高位借1
        n1 = reverse(n1);
        n2 = reverse(n2);

        Node p = n1;
        Node q = n2;

        Node browNode;

        while (p != null && q != null) {

            // 向高位借1
            if (p.val < q.val) {
                browNode = p.next;
                //高位为0，继续向高位借，路过的高位直接置为9
                while (browNode.val == 0) {
                    browNode.val = 9;
                    browNode = browNode.next;
                }
                browNode.val = browNode.val -1;
                p.val = p.val + 10;
            }
            p.val = p.val - q.val;

            p = p.next;
            q = q.next;
        }

        return reverse(n1);
    }

    static Node reverse(Node head) {
        Node pre = null;
        Node current = head;

        while (current != null) {
            Node temp = current.next;
            current.next = pre;
            pre = current;
            current = temp;
        }
        return pre;
    }
}
